# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        mid_list = []
        while head:
            if head in mid_list:
                break
            mid_list.append(head)
            head = head.next
        return head


class Solution2(object):
    def detectCycle(self, head):
        i1, i2, flag = head, head, False
        while i1 and i2:
            try:
                i1 = i1.next
                i2 = i2.next.next
                if i1 is i2:
                    flag = True
                    break
            except:
                break
        if not flag:
            return None
        i2 = head
        while i1 is not i2:
            i1 = i1.next
            i2 = i2.next.next
        return i1
